# 作者:MRHyy
# 2025年02月23日14时08分35秒
import random
#完成二叉树中序，后序，层序遍历
class Node:

    def __init__(self, elem=-1, lchild=None, rchild=None):
        self.elem = elem
        self.lchild = lchild
        self.rchild = rchild


class Tree:

    def __init__(self):
        self.root = None
        self.queue = []

    def add_node(self, elem):
        new_node: Node = Node(elem)
        self.queue.append(new_node)
        if self.root is None:
            self.root = new_node
        else:
            if self.queue[0].lchild is None:
                self.queue[0].lchild = new_node
            else:
                self.queue[0].rchild = new_node
                self.queue.pop(0)

    def preorder(self, current_node: Node):
        if current_node:
            print(current_node.elem, end=' ')
            self.preorder(current_node.lchild)
            self.preorder(current_node.rchild)

    def inorder(self, current_node: Node):
        if current_node:
            self.inorder(current_node.lchild)
            print(current_node.elem, end=' ')
            self.inorder(current_node.rchild)

    def postorder(self, current_node: Node):
        if current_node:
            self.postorder(current_node.lchild)
            self.postorder(current_node.rchild)
            print(current_node.elem, end=' ')

    def levelorder(self):
        queue = []
        queue.append(self.root)
        while queue:
            current_node = queue.pop(0)
            print(current_node.elem, end=' ')
            if current_node.lchild:
                queue.append(current_node.lchild)
            if current_node.rchild:
                queue.append(current_node.rchild)


if __name__ == '__main__':
    t = Tree()
    for i in range(1, 11):
        t.add_node(i)
    t.preorder(t.root)
    print()
    print('-' * 50)
    t.inorder(t.root)
    print()
    print('-' * 50)
    t.postorder(t.root)
    print()
    print('-' * 50)
    t.levelorder()

# 堆排序，快排
class Sort:
    def __init__(self, n, nums_range):
        self.n = n
        self.arr = []
        self.nums_range = nums_range
        self.random_nums()

    def random_nums(self):
        for i in range(self.n):
            self.arr.append(random.randint(1, self.nums_range - 1))


    def partition(self,low,high):
        arr = self.arr
        pivot = low
        for i in range(low, high):
            if self.arr[i] <= pivot:
                arr[i], arr[pivot] = arr[pivot], arr[i]
            pivot += 1
        arr[pivot], arr[high] = arr[high], arr[pivot]
        return pivot

    def QuickSort(self, low, high):
        if low < high:
            pivotpos = self.partition(low, high)
            self.QuickSort(low, pivotpos-1)
            self.QuickSort(pivotpos + 1, high)


    def adjust_max_heap(self, parent_pos, arr_len):
        arr = self.arr
        dad = parent_pos
        son = dad * 2 + 1
        while son < arr_len:
            if son + 1 < arr_len and arr[son] < arr[son + 1]:
                son = son + 1
            if arr[dad] < arr[son]:
                arr[dad], arr[son] = arr[son], arr[dad]
                dad = son
                son = dad * 2 + 1
            else:
                break

    def heap_sort(self):
        arr = self.arr
        for parent_pos in range(len(self.arr)-1, -1, -1):
            self.adjust_max_heap(parent_pos, self.n)
        for end_pos in range(len(self.arr)-1, 0, -1):
            arr[end_pos], arr[0] = arr[0], arr[end_pos]
            self.adjust_max_heap(0, end_pos)

if __name__ == '__main__':
    s = Sort(10,100)
    print(s.arr)
    s.heap_sort()
    print(s.arr)

